(a) Field of the Invention
The present invention relates to an interconnection routing method for an integrated circuit, and more particularly, to an interconnection routing method for a high performance integrated circuit, by reducing electric interaction induced between the interconnections which has an influence on circuit performance, such as increase of crosstalk or coupled capacitance between the interconnections.
(b) Description of the Related Art
A conventional interconnection routing method for an integrated circuit generally involves manual modification (first method), after an optimized and detailed interconnection design is completed by a channel routing, in order to reduce the number of crossings between the interconnections.
Two other methods are further used, in addition to the first method as described above, in order to limit lengths of adjacent and parallel running interconnections. One is employed to increase the spacing between the interconnections using a compactor (second method) and the other is employed to permutate the tracks for the interconnections in a channel area (third method).
For example, those conventional methods are described in a document entitled "Minimum Crosstalk Channel Routing", IEEE ICCAD' 1993, Tong, Gao et al. p692-696.
The first method for the manual modification is carried out based on information for coupled capacitance and crosstalk obtained from the result of detailed interconnection routing given by the previous processing.
In detail, the modification is carried out by a partial permutation of the resultant nets of interconnections involving a layout problem. The modifications may include rip-up and reroute of target nets, or moving some of the resultant nets to enlarge the spacing therebetween.
Referring to FIGS. 1A and 1B, crosstalk induced between net a and net e is reduced in FIG. 1B by permutating the track for the net e, for a given detailed interconnection routing shown in FIG. 1A. Alternatively, as shown in FIG. 1C, the modification is carried out so as to reduce the crosstalk by inserting an empty track between the nets a and net e which are likely to cause a crosstalk problem, thereby enlarging the spacing therebetween.
The second method using the compactor is such that the process for enlarging the spacing between the nets in the manual modification as described above is carried out by an automated compaction process. In general, the compaction process is carried out in the procedure shown in FIG. 2 by a compactor.
In FIG. 2, the compaction process includes the steps S101 through S103. Step S101 involves extraction of information as to crosstalk in which a set P for net pairs (net n and net n') inducing crosstalk therebetween is extracted from a given interconnection routing such as shown in FIG. 1A. Step S102 involves constraint introduction as to spacing between the pair in which a constraint is introduced such that the spacing between the pair, e.g., net n and net n' is equal to or larger than a threshold, or a target spacing. Step S103 involves compaction processing in which the space between respective net pairs included in the set P is enlarged, in addition to a design rule not to violate vertical constraints. FIG. 1C shows the resultant interconnection routing obtained by the compaction process applied to the given interconnection routing shown in FIG. 1A.
In FIG. 1C, in a central portion of the channel area, the empty track is inserted between the tracks for net a and net e running adjacent and parallel to each other. The crosstalk induced between net a and net e is reduced accordingly.
The third method, in which adjacent nets inducing crosstalk therebetween are moved away from each other by permutating tracks assigned to whole interconnections using a known track assignment process, includes three steps as described below. FIG. 3 shows the process flow thereof.
In FIG. 3, step S201 involves extraction of adjacent nets in which a set R(n) of nets adjacent to a net n is formed from a given interconnection routing.
Step S202 involves calculation by a detailed function CT(n,m) for crosstalk, in which calculation by the crosstalk function CT(n,m) is executed based on the length l(n,m) of the path along which net n and net m run adjacent and parallel to each other and on the distance d(n,m) between the net n and net m, for the net m belonging to the set R(n) and running adjacent and parallel to a specified net n. For example, the crosstalk function CT(n,m) is represented by k.multidot.1(n,m)/d(n,m), wherein k is a constant.
Last step S203 involves permutation of tracks, in which the track number for each net is determined by calculation using a linear programming method so as to minimize the maximum value of the evaluation function CT for all the net pairs existing in the channel area.
By applying the third method to the given interconnection routing shown in FIG. 1A, the crosstalk is reduced through permutation of track 1 with track 2 to enlarge the spacing between the trunks of the net a and net e. The resultant routing is shown in FIG. 1D.
As described above, the conventional methods for the interconnection routing in the integrated circuit are employed to reduce electric interactions induced between the interconnections and causing increase of the coupled capacitance and the crosstalk, by limiting the lengths of adjacent and parallel running interconnections.
Reduction of the number of the crossings in an integrated circuit and limitation on the lengths of the adjacent and parallel running interconnections are important in order to avoid reduction in operation speed due to increase of the coupled capacitance or signal errors due to crosstalk. However, in the conventional methods, there are problems, such as errors in manual modification and increase in amount of processing time associated with after-treatment, resulting from repetitive practices directed to optimization after the compaction process.
Further, it is difficult to insure an optimal design for a final interconnection routing because of after-treatment executed for the optimized and given interconnection routing. There is also a problem that it is difficult to obtain an acceptable solution because of the vertical constraints.